#include <stdio.h>

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/**
 * 核心思想：
 * 若前一个元素大于0，则将其加到当前元素上
 * 
 * dp[i] 表表示nums中以nums[i]结尾的最大子序和
 * dp[i] = max(dp[i-1]+nums[i], nums[i]);
 * dp[i]是当前数字，要么是与前面的最大子序和的和
 */


SElemType max_element(SElemType * arr, int arrSize)
{
    SElemType maxElement = INF;
    for (int i = 0; i < arrSize; ++i){
        maxElement = maxElement > arr[i] ? maxElement : arr[i];
    }
    return maxElement;
}

SElemType max(SElemType a, SElemType b){
    return a>b?a:b;
}

int maxSubArray(int* nums, int numsSize)
{
    int i;
    SElemType ans;
    for (i = 1; i < numsSize; i++)
    {
        nums[i] = max((nums[i-1] + nums[i]), nums[i]);
    }
    ans = max_element(nums, numsSize);
    return ans;
}


int main(int argc, char** argv){
    SElemType nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int numsSize = sizeof(nums)/sizeof(nums[0]);
    int ans = INF;
    ans = maxSubArray(nums, numsSize);

    printf("%d\n", ans);

    return 0;
}